package LRU

import (
    "container/heap"
    "time"
    "strconv"
)

type HeapNode struct {
    value   int
    deadline time.Time
}

type TimeoutHeap []*HeapNode

func (h TimeoutHeap) Len() int {
    return len(h)
}

func (h TimeoutHeap) Less(i, j int) bool {
    return h[i].deadline.Before(h[j].deadline) // 小根堆
}

func (h TimeoutHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *TimeoutHeap) Push(x interface{}) {
    *h = append(*h, x.(*HeapNode))
}

func (h *TimeoutHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// 向缓存中添加数据
func (tc *TimeoutCache) Add(key int, value string, timeout int) {
    // 超时的时间点
    deadline := time.Now().Add(time.Duration(timeout) * time.Second)
    if len(tc.cache) == tc.cap { // 缓存已满
        top := tc.hp[0]
        if top.deadline.Before(deadline) { // 如果堆顶元素过期，就删除
            heap.Pop(&tc.hp)
            delete(tc.cache, top.value)
        } else {
            return
        }
    }
    // 把key,value放到map
    tc.cache[key] = &HeapNode{value: key, deadline: deadline}
    heap.Push(&tc.hp, &HeapNode{value: key, deadline: deadline})
}

func (tc *TimeoutCache) Get(key int) (string, bool) {
    node, ok := tc.cache[key]
    if !ok {
        return "", false
    }
    return strconv.Itoa(node.value), ok
}

// 超时缓存，不支持并发
type TimeoutCache struct {
    cache map[int]*HeapNode // 存储业务数据
    hp    TimeoutHeap       // 超时堆
    cap   int               // 缓存容量
}

func NewTimeoutCache(cap int) *TimeoutCache {
    tc := new(TimeoutCache)
    tc.cache = make(map[int]*HeapNode, cap)
    tc.hp = make(TimeoutHeap, 0, 10)
    tc.cap = cap
    heap.Init(&tc.hp) // 初始化堆
    go tc.taotail() // 启动goroutine定期清理过期缓存项
    return tc
}

// 不停地检测堆顶元素是否超时，超时的话就删除
func (tc *TimeoutCache) taotail() {
    for {
        if tc.hp.Len() == 0 {
            time.Sleep(100 * time.Millisecond)
            continue
        }
        now := time.Now()
        top := tc.hp[0]
        if top.deadline.Before(now) {
            heap.Pop(&tc.hp)
            delete(tc.cache, top.value)
        }
        time.Sleep(100 * time.Millisecond)
    }
}